package main

import "fmt"

//#link: https://leetcode-cn.com/problems/beautiful-arrangement/
func main() {
	n := 2
	fmt.Println(countArrangement(n))
}

//计算优美排列
func countArrangement(n int) (ans int) {
	//是否访问过
	visited := make([]bool, n+1)
	//预处理,用来提前加好i位可以放置的数字
	match := make([][]int, n+1)
	for i := 1; i <= n; i++ {
		for j := 1; j <= n; j++ {
			if i%j == 0 || j%i == 0 {
				match[i] = append(match[i], j)
			}
		}
	}

	var backtrack func(int)
	backtrack = func(index int) {
		//回溯结束条件为 当前队列长度大于n时
		if index > n {
			ans++
			return
		}
		for _, x := range match[index] {
			if !visited[x] {
				visited[x] = true
				backtrack(index + 1)
				//回溯回退
				visited[x] = false
			}
		}
	}
	backtrack(1)
	return
}
